package backtracking.leetcode.medium;

/**
 * @author bruin_du
 * @description 矩阵中的路径
 * @date 2022/5/27 16:27
 **/
public class Exist {
    public boolean exist(char[][] board, String word) {
        char start = word.charAt(0);
        int row = board.length,col = board[0].length;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if(board[i][j] == start){
                    if(find(board,i,j,word,0))
                        return true;
                }
            }
        }
        return false;
    }

    private boolean find(char[][] board, int i, int j,String word, int index) {
        if(i < 0 || i >= board.length || j < 0 || j >= board[0].length ||
                board[i][j] != word.charAt(index) )
            return false;
        if(index == word.length() - 1) return true;
        board[i][j] = '\0';
        boolean ret  = find(board, i + 1, j,  word, index + 1)||
                        find(board, i - 1, j, word, index + 1)||
                        find(board, i , j + 1, word, index + 1)||
                        find(board, i , j - 1, word, index + 1);
        board[i][j] = word.charAt(index);
        return ret;
    }
}
